package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

public class MajorityElement {

	public static void main(String[] args) {
		int[] nums = {3, 2, 2};
		MajorityElement object = new MajorityElement();
		System.out.println(object.majorityElement(nums));
	}
	
	public List<Integer> majorityElement(int[] nums) {
        //find times more than nums.length / 3
        List<Integer> list = new ArrayList<>();
        if(nums == null || nums.length <= 0){
            return list;
        }
        int k = 3;
        int times = nums.length / 3;
//        if(k < 1){
//        	Set<Integer> set = new LinkedHashSet<>();
//        	for (int i = 0; i < nums.length; i++) {
//        		set.add(nums[i]);
//			}
//        	list.addAll(set);
//            return list;
//        }
        HashMap<Integer, Integer> candidates = new HashMap<>();
//        if(k == 1){
//        	for(int i = 0; i < nums.length; i++){
//                if(candidates.containsKey(nums[i])){
//                    candidates.put(nums[i], candidates.get(nums[i]) + 1);
//                }else {
//                    candidates.put(nums[i], 1);
//                }
//            }
//        	for(Entry<Integer, Integer> entry : candidates.entrySet()){
//        		if(entry.getValue() > 1){
//        			list.add(entry.getKey());
//        		}
//        	}
//        	return list;
//        }
        for(int i = 0; i < nums.length; i++){
            if(candidates.containsKey(nums[i])){
                candidates.put(nums[i], candidates.get(nums[i]) + 1);
            }else {
                if(candidates.size() == k - 1){
                    allCandisMinusOne(candidates);
                }else{
                	candidates.put(nums[i], 1);
                }
            }
        }
        HashMap<Integer, Integer> reals = getReals(nums, candidates);
        for(Entry<Integer, Integer> set : reals.entrySet() ){
            Integer key = set.getKey();
            Integer value = set.getValue();
            if(value > times){
            	list.add(key);
            }
        }
        return list;
    }
    
    private void allCandisMinusOne(HashMap<Integer, Integer> candidates){
        List<Integer> removeList = new LinkedList<>();
        for(Entry<Integer, Integer> set : candidates.entrySet() ){
            Integer key = set.getKey();
            Integer value = set.getValue();
            System.out.println("key:" + key + " value:" + value);
            if(value == 1){
                removeList.add(key);
            }
            candidates.put(key, value - 1);
        }
        for(Integer removeKey : removeList){
            candidates.remove(removeKey);
        }
    }
    
    public HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> candidates){
        HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>();
        for(int i = 0; i < arr.length; i++){
            int curNum = arr[i];
            if(candidates.containsKey(curNum)){
                if(reals.containsKey(curNum)){
                    reals.put(curNum, reals.get(curNum) + 1);
                }else{
                    reals.put(curNum, 1);
                }
            }
        }
        return reals;
    }
}
